package 纯数组;

import java.util.Arrays;

public class No875爱吃香蕉的珂珂 {

    /**
     * 珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
     * 珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。
     * 每个小时，她将会选择一堆香蕉，从中吃掉 K 根。
     * 如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  
     * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
     * 返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
     *
     * 示例 1：
     * 输入: piles = [3,6,7,11], H = 8
     * 输出: 4
     * 示例 2：
     * 输入: piles = [30,11,23,4,20], H = 5
     * 输出: 30
     * 示例 3：
     * 输入: piles = [30,11,23,4,20], H = 6
     * 输出: 23
     *  
     * 提示：
     * 1 <= piles.length <= 10^4
     * piles.length <= H <= 10^9
     * 1 <= piles[i] <= 10^9
     */

    /**
     * 与No1011题不同的是此题可以选择吃,我们就将其排序,然后二分最优
     */
    public int minEatingSpeed(int[] piles, int h) {

        Arrays.sort(piles);
        long sum=0;
        for (int pile : piles) {
            sum+=pile;
        }

        //不能从1开始吃
        long left=1;
        long right=sum;
        long mid;

        while (left<=right){
            mid=(right-left)/2+left;
            boolean isOk=isOk(piles,h,mid);
            if(isOk){
                //时间够,慢点吃
                right=mid-1;
            }else{
                //不够,快点吃
                left=mid+1;
            }
        }

        return (int) left;
    }

    private boolean isOk(int[] piles,int h,long m) {
        int hCount=0;
        //一次可吃下m根
        for (int i = 0; i < piles.length;i++) {

            long spendH;
            if(piles[i]<=m){
                spendH=1;
            }else{
                //花费的小时
                spendH=piles[i]/m;
                //一次吃不完,吃一点先
                if(piles[i]%m!=0){
                    spendH++;
                }
            }

            hCount+=spendH;
            if(hCount>h){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        No875爱吃香蕉的珂珂 n=new No875爱吃香蕉的珂珂();
        int[] arr={332484035,524908576,855865114,632922376,222257295,690155293,112677673,679580077,337406589,290818316,877337160,901728858,679284947,688210097,692137887,718203285,629455728,941802184};
        int result = n.minEatingSpeed(arr, 823855818);
        System.out.println(result);
    }

}
